package top.humbleyuan.sword;

import org.junit.Test;
import top.humbleyuan.leet.Array;
import top.humbleyuan.sword.util.MyUtil;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @Author HumbleYuan
 * @Date 2019/12/19 15:26
 * @Des 剑指offer练习题
 * 需要注意的题：
 *      二叉树中某一值的路径
 *
 */
public class InterviewQ {

    /**
     * 找到重复数字
     */
    @Test
    public void p39_q3() {
        int length = 10;
        int[] arr = MyUtil.getMyUtil().formArray(length);
        System.out.println(Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));

        int cur = arr[0];
        List<Integer> sameList = new ArrayList<>();

        for (int i = 1; i < arr.length; i++) {
            // 若下一个不同直接往下
            if(cur != arr[i]) {
                cur = arr[i];
                continue;
            }
            // 找到相同元素加入
            sameList.add(arr[i]);

            // 由于有序，做循环过滤掉相邻相同的元素
            do {
                i++;
            } while (i < arr.length && cur == arr[i]);

            // 过滤掉上一个相同元素后，直接跳到下一组
            if(i < arr.length) {
                cur = arr[i];
            }
        }

        if(sameList == null || sameList.size() == 0) {
            System.out.println("无重复元素");
            return;
        }
        for (Integer i:sameList) {
            System.out.print(i + ", ");
        }
    }

    @Test
    public void p39_q3_2() {
        /**
         * 因为长度和每个数范围相同，若不存在相同数，则每个数组的index应该与对应数值相等
         * 思想:将每个数组移到数组对应index上，若该index上的数与当前数相等，则此数为重复数字
         * 但是得到的重复集合中依然有重复。。
         */
        int length = 8;
        int[] arr = MyUtil.getMyUtil().formArray(length);
        System.out.println(Arrays.toString(arr));

        List<Integer> sameList = new ArrayList<>();

        for(int i = 0; i < length; i++) {
            if(arr[i] == i){
                continue;
            }

            if(arr[i] == arr[arr[i]]) {
                sameList.add(arr[i]);
            }else {
                int temp = arr[i];
                arr[i] = arr[arr[i]];
                arr[temp] = temp;
                i--;
            }
        }

        if(sameList == null || sameList.size() == 0) {
            System.out.println("无重复元素");
            return;
        }
        for (Integer i:sameList) {
            System.out.print(i + ", ");
        }

    }

    /**
     * 搜索二维数组
     */
    @Test
    public void p44_q4() {
        int[][] sortedArray = {{1, 2, 3, 5, 6, 19},
                                {2, 4, 5, 6, 8, 20},
                                {3, 5, 6, 8, 9, 24},
                                {5, 8, 9, 10, 11, 27},
                                {10, 11, 12, 13, 14, 30}};
        int s = 10;

        if(sortedArray == null || sortedArray.length == 0 || sortedArray[0].length == 0) {
            System.out.println("不存在");
            return;
        }

        int rEnd = sortedArray.length - 1;
        int cEnd = sortedArray[0].length - 1;

        int rStart = 0, cStart = 0;

        /**
         * 从矩阵角落逐步剔出行或列
         * 从右上角开始
         */
        while (rStart <= rEnd && cStart <= cEnd) {
            if(sortedArray[rStart][cEnd] > s) {
                cEnd--;
            }else if(sortedArray[rStart][cEnd] < s) {
                rStart++;
            }else {
                System.out.println("存在，是sortedArray[" + rStart +"][" + cEnd + "]");
                return;
            }
        }

        System.out.println("不存在");
    }

    /**
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
     * 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
     * 并保证奇数和奇数，偶数和偶数之间的相对位置不变
     */
    @Test
    public void niuke_13() {
        int[] array = {1,2,3,4,5,6,7};
        // 空间换时间
        int[] newArray = new int[array.length];
        int cur = 0;
        for(int i = 0;i < array.length;i++) {
            if(array[i] % 2 == 1) {
                newArray[cur++] = array[i];
            }
        }

        for(int i = 0;i < array.length;i++) {
            if(array[i] % 2 == 0) {
                newArray[cur++] = array[i];
            }
        }
        array = newArray;

        System.out.println(Arrays.toString(array));
    }

    /**
     * 顺时针打印矩阵
     */
    @Test
    public void niuke_shunshizhen() {
        int[][] matrix = {{1,2,3,4}};
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            System.out.println("空");
            return ;

        }
        ArrayList<Integer> sorted = new ArrayList<>();
        int maxI = matrix.length - 1, minI = 0;
        int maxJ = matrix[0].length - 1, minJ = 0;

        // 转一圈一个循环
        while(true) {
            // 上面行
            for(int j = minJ;j <= maxJ; j++) {
                sorted.add(matrix[minI][j]);
            }

            // ** 一旦不满足最大行最小行关系就可以退出，
            // 因为此时无论行和列都没有必要再去遍历
            if(++minI > maxI) {
                break;
            }

            // 右边列
            for(int i = minI;i <= maxI; i++) {
                sorted.add(matrix[i][maxJ]);
            }

            if(--maxJ < minJ) {
                break;
            }


            // 下边行
            for(int j = maxJ;j >= minJ; j--) {
                sorted.add(matrix[maxI][j]);
            }

            if(--maxI < minI) {
                break;
            }


            // 左边列,并且大于一列
            for(int i = maxI;i >= minI; i--) {
                sorted.add(matrix[i][minJ]);
            }

            if(++minJ > maxJ) {
                break;
            }
        }

        System.out.println(sorted);
    }

    /**
     * 栈的压入弹出顺序是否符合
     */
    @Test
    public void niuke_zhanyaru() {
        int[] pushA = {1,2,3,4,5};
        int[] popA = {3,5,4,1,2};

        if(pushA == null || popA == null) {
            System.out.println(false);
            return;
        }
        ArrayList<Integer> curStack = new ArrayList<>();
        int i,j = 0;
        for(i = 0; i < popA.length;i++) {
            // 先判断list的末尾表示栈顶是否是当前popA第一个
            if(curStack != null && curStack.size() > 0
                    && curStack.get(curStack.size() - 1) == popA[i]) {
                curStack.remove(curStack.size() - 1);
                j++;
                continue;
            }

            // 若非栈顶，将pushA中数压入直到出现当前popA中数
            for(;j < pushA.length && popA[i] != pushA[j];j++) {
                curStack.add(pushA[j]);
            }

            // 未找到popA当前元素
            if(j >= pushA.length) {
                System.out.println(false);
                return ;
            }else {
                j++;
            }
        }
        System.out.println(true);
    }


    /**
     * 验证一组数是不是二叉搜索树的后序遍历
     */
    @Test
    public void niuke_searchTree() {
        int[] s = {4,6,7,5};
        System.out.println(VerifySquenceOfBST(s));
    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0 || sequence.length == 1) {
            return true;
        }

        int i;
        for(i = 0;i < sequence.length - 1;i++) {
            // 找到所有左子树
            if(sequence[i] > sequence[sequence.length - 1]) {
                break;
            }
        }
        // 所有左子树,注意左右子树都不能将根节点放入
        int[] left = Arrays.copyOf(sequence, i);
        int[] right = Arrays.copyOfRange(sequence, i, sequence.length - 1);
        // 验证右子树中是否有小于根的
        for(int j = i + 1;j < sequence.length;j++) {
            // 找到不符合的
            if(sequence[j] < sequence[sequence.length - 1]) {
                return false;
            }
        }
        return VerifySquenceOfBST(left) && VerifySquenceOfBST(right);
    }

    /**
     * 找数组中最小k个数
     */
    @Test
    public void getSmallestK() {
        // 不使用优先级队列，自己构造堆

        getSmallestKWithHead();

//        int[] nums = {4,5,1,6,2,7,3,8};
//        int k =4;
//        /**
//         * 创建一个集合存储k个最小值，
//         * 每次遍历数组，依次和最大的数比较，若比某个数小，则挤掉最大数，并插入并有序
//         * 1. 使用大顶堆
//         * 2. 使用prorityQueue
//         */
//
//        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2.compareTo(o1);
//            }
//        });
//
//        for (int i = 0; i < nums.length; i++) {
//            // 未满
//            if(queue.size() != k) {
//                queue.offer(nums[i]);
//                continue;
//            }
//
//            // 替换
//            if(queue.peek() > nums[i]) {
//               queue.poll();
//               queue.offer(nums[i]);
//            }
//        }
//
//        System.out.println(queue.toString());
    }

    public void getSmallestKWithHead() {

        int[] nums = {4,5,1,6,2,7,3,8};
        int k = 4;

        int[] priority = new int[k];
        boolean flag = false;

        for (int i = 0; i < nums.length; i++) {
            if(i < k) {
                priority[i] = nums[i];
                continue;
            }

            // 满了进行构造
            if(!flag) {
                flag = true;
                for (int j = (k >> 1) - 1; j >= 0; j--) {
                    buildMaxHeap(j, priority,k);
                }
            }

            // 不用每次都重复构造
            if(priority[0] > nums[i]) {
                priority[0] = nums[i];
                buildMaxHeap(0,priority,k);
            }

        }

        Integer[] ii = Arrays.stream(priority).boxed().toArray(Integer[]::new);
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(ii));
        System.out.println(Arrays.toString(priority));
    }

    public void buildMaxHeap(int i, int[] p,int len) {
        int temp = p[i];
        // 从当前点的第一个左孩子
        for (int j = i * 2 +1; j < len; j = j * 2 +1) {
            if(j + 1 < len && p[j] < p[j+1]) {
                j++;
            }

            // 追溯比较点移动
            if(p[j] > temp) {
                p[i] = p[j];
                i = j;
            }else {
                break;
            }
        }
        p[i] = temp;

    }


    class TreeNode{

        HashSet<Integer> set = new HashSet<>();

        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }





}
